package com.hanxiaozhang.no10leetcode.link;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给两个数字m，n，从m 到n 的位置翻转该链表，请在一次循环内完成操作
 * 实例:
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 * <p>
 * Tips：
 * 这个只能背了，总是忘记
 *
 * @author hanxinghua
 * @create 2024/1/31
 * @since 1.0.0
 */
public class No92ReverseLinkedListII {


    public static void main(String[] args) {

        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);

        Node reverse = reverseBetween(head, 2, 4);
        LinkUtil.printLink(reverse);

    }

    /*
      一、count = 2，即开始位置 ：
                  pre  cur
     dummyHead -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL

     # 1. next = cur.next
                  pre  cur  next
     dummyHead -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL

     # 2. cur.next = cur.next.next
                  pre  cur  next
     dummyHead -> 1 -> 2   3 -> 4 -> 5 -> NULL
                        \ _ _ /^

     # 3. next.next = pre.next
                  pre  cur  next
     dummyHead -> 1 -> 2 <- 3   4 -> 5 -> NULL
                        \ _ _ /^

     # 4. pre.next = next
                  pre  cur  next
                      _ _
                   /       \.
     dummyHead -> 1 -> 2 <- 3   4  ->  5 -> NULL
                       \  _ _  /^

     # 整理结果：
                  pre  next   cur
     dummyHead -> 1 ->  3 ->  2  -> 4 - > 5 -> NULL


      二、count = 3 ：
                  pre  next   cur
     dummyHead -> 1 ->  3 ->  2  -> 4 - > 5 -> NULL

     # 1. next = cur.next
                  pre      cur  next
     dummyHead -> 1 -> 3 -> 2 -> 4 - > 5 -> NULL

     # 2. cur.next = cur.next.next
                  pre      cur  next
     dummyHead -> 1 -> 3 -> 2   4 - > 5 -> NULL
                             \  _ _  /^

     # 3. next.next = pre.next
                 pre       cur  next
                           _ _
                       ./      \
     dummyHead -> 1 -> 3 -> 2   4   5 -> NULL
                            \  _ _  /^

     # 4. pre.next = next
                 pre      cur  next
                       _ _ _ _ _
                     /      _ _  \
                   /    ./      \ \.
     dummyHead -> 1    3 -> 2    4    5 -> NULL
                            \  _ _ _ /^

     # 整理结果：
                  pre  next     cur
     dummyHead -> 1 -> 4 -> 3 -> 2 -> 5 -> NULL



     */


    public static Node reverseBetween(Node head, int m, int n) {
        // 傀儡头节点
        Node dummyHead = new Node(-1);
        dummyHead.next = head;

        // 前继 dummyHead  ； 当前 head ； 后继 next
        Node pre = dummyHead, cur = head, next = null;
        int count = 1;

        // 注意： count < n
        while (cur != null && count < n) {
            // 交换的开始位置  && cur.next 不为空
            if (count >= m && cur.next != null) {
                // 记录当前节点后继节点
                next = cur.next;
                // 当前节点的后继 指向 当前节点的后继的后继
                cur.next = cur.next.next;
                // 当前节点后继节点（next）的后继 指向 pre的后继节点
                next.next = pre.next;
                //  pre的后继节点 指向 当前节点后继节点（next）
                pre.next = next;
            } else {
                // 后移一步
                pre = pre.next;
                cur = cur.next;
            }
            count++;
        }
        return dummyHead.next;
    }

}
